package leetcode.code1202;

import java.util.HashMap;
import java.util.List;
import java.util.Map;

import leetcode.IDebug;
import leetcode.helper.HelpDebug;

//执行用时：25 ms, 在所有 Java 提交中击败了97.83%的用户
//
//内存消耗：90.1 MB, 在所有 Java 提交中击败了23.11%的用户
//
//通过测试用例：36 / 36

public class Solution implements IDebug {

	public String smallestStringWithSwaps(String s, List<List<Integer>> pairs) {
		int n = s.length();
		Union union = new Union(n);
		for (List<Integer> pair : pairs) {
			union.merge(pair.get(0), pair.get(1));
		}
		int[][] dics = new int[union.group][26];
		Map<Integer, Integer> ri = union.mapper();
		char[] cs = s.toCharArray();
		for (int i = 0; i < n; i++) {
			int root = union.findRoot(i);
			int cur = cs[i] - 'a';
			int index = ri.get(root);
			dics[index][cur]++;
		}
		int[] pts = new int[union.group];
		StringBuffer sb = new StringBuffer();
		for (int i = 0; i < n; i++) {
			int root = union.findRoot(i);
			int index = ri.get(root);
			while (dics[index][pts[index]] == 0) {
				pts[index]++;
			}
			sb.append((char) ('a' + pts[index]));
			dics[index][pts[index]]--;
		}
		return sb.toString();
	}

	class Union {
		int n;
		int[] roots;
		int[] sizes;
		int[] stack;
		int p;
		int group;

		public Union(int n) {
			this.n = n;
			roots = new int[n];
			sizes = new int[n];
			for (int i = 0; i < n; i++) {
				roots[i] = i;
				sizes[i] = 1;
			}
			stack = new int[n];
			group = n;
		}

		public Map<Integer, Integer> mapper() {
			Map<Integer, Integer> ans = new HashMap<>();
			int k = 0;
			for (int i = 0; i < n; i++) {
				int s = this.sizes[i];
				if (s != 0) {
					ans.put(i, k++);
				}
			}
			return ans;
		}

		public void merge(int idx1, int idx2) {
			int root1 = this.findRoot(idx1);
			int root2 = this.findRoot(idx2);
			if (root1 != root2) {
				int size1 = this.sizes[root1];
				int size2 = this.sizes[root2];
				if (size1 > size2) {
					this.roots[root2] = root1;
					this.sizes[root1] = size1 + size2;
					this.sizes[root2] = 0;
				} else {
					this.roots[root1] = root2;
					this.sizes[root2] = size1 + size2;
					this.sizes[root1] = 0;
				}
				group -= 1;
			}
		}

		private int findRoot(int idx1) {
			int p = 0;
			int ans = 0;
			while ((ans = this.roots[idx1]) != idx1) {
				this.stack[p++] = idx1;
				idx1 = ans;
			}
			while (p > 0) {
				this.roots[this.stack[--p]] = ans;
			}
			return ans;
		}
	}

	@Override
	public void debug1() {
		HelpDebug.compare("abcd", this.smallestStringWithSwaps("dcab", HelpDebug.str2intlist1("[[0,3],[1,2],[0,2]]")));

	}

	@Override
	public void debug2() {
		HelpDebug.compare("bacd", this.smallestStringWithSwaps("dcab", HelpDebug.str2intlist1("[[0,3],[1,2]]")));

	}

	@Override
	public void debug3() {
		HelpDebug.compare("abc", this.smallestStringWithSwaps("cba", HelpDebug.str2intlist1("[[0,1],[1,2]]")));

	}

	@Override
	public void debug4() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

}
